package 剑指offer;

import java.util.Arrays;

public class 剑指Offer41数据流中的中位数 {  double[] arr = null;
    int count = 0;
    /** initialize your data structure here. */
    public 剑指Offer41数据流中的中位数() {
        this.arr = new double[16];
    }

    public void addNum(int num) {
        arr[count] = (num * 1.0);
        count++;
        Arrays.sort(arr,0,count);
        if(arr.length - count < 8){
            double[] arr1 = new double[arr.length + 16];
            for(int i = 0 ; i < count ; i++){
                arr1[i] = arr[i];
            }
            this.arr = arr1;
        }
    }

    public double findMedian() {
        int size = count;
        if(size % 2 == 0){//偶数个
            return (arr[size / 2 - 1] + arr[(size) / 2]) / 2.0;
        }else{
            int index = size/ 2 ;
            return arr[index]* 1.0;
        }
    }

    public static void main(String[] args) {
        剑指Offer41数据流中的中位数 o = new 剑指Offer41数据流中的中位数();
        o.addNum(1);
        System.out.println(o.findMedian());

        o.addNum(2);
        System.out.println(o.findMedian());

        o.addNum(3);
        System.out.println(o.findMedian());

        o.addNum(4);
        System.out.println(o.findMedian());
        o.addNum(5);
        System.out.println(o.findMedian());

        o.addNum(6);
        System.out.println(o.findMedian());

        o.addNum(7);
        System.out.println(o.findMedian());

        o.addNum(8);
        System.out.println(o.findMedian());

        o.addNum(9);
        System.out.println(o.findMedian());

        o.addNum(10);
        System.out.println(o.findMedian());

        o.addNum(11);
        System.out.println(o.findMedian());

        o.addNum(12);
        System.out.println(o.findMedian());


    }
}
